#include <iostream>
#include <string>
#include <vector>
#include "BinaryTree.h"
using namespace std;

// 97.42 %
class Solution
{
  public:
	TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
	{
		if (!root)
			return NULL;
		if (p->val < root->val && q->val < root->val)
		{
			return lowestCommonAncestor(root->left, p, q);
		}
		else if (p->val > root->val && q->val > root->val)
		{
			return lowestCommonAncestor(root->right, p, q);
		}
		return root;
	}
};

int main()
{
	int arr[] = {6, 2, 1, 0, 0, 4, 3, 0, 0, 5, 0, 0, 8, 7, 0, 0, 9, 0, 0};
	int n = sizeof(arr) / sizeof(arr[0]);
	TreeNode *tree = createBinaryTree(arr, n);
	int sum = 8;
	preorderPrint(tree);
	cout << endl;
	cout << Solution().lowestCommonAncestor(tree, tree->left, tree->left->right)->val << endl;
	deleteBinaryTree(tree);
	return 0;
}
